This invention is related to the reliability of arithmetic hardware in computer processors, and in particular, it relates to residue checking in computer processors.
One way to ensure reliability in computer processor adders and multipliers is to check the results using a parallel circuit that calculates the residue of the operands and compares an expected residue to the actual residue of the result.
Residue checking may be utilized to provide protection from transient failures and/or early end of life failures in arithmetic circuits.
Modulus-15 residue generators have been utilized with binary/hexadecimal formatted numbers to check arithmetic circuits. The modulus-15 residue of an operand is the remainder of dividing the operand by 15. In this case, the modulus is one less than a hexadecimal systems radix. All powers of 16 have a remainder of 1 in a modulus-15 system. Due to this, the modulus-15 residue of a binary number is simply the sum of its hexadecimal digits. This may be represented as follows:X=Σxj16j;res X=res(Σres(res(xj)res(16j))), where res(16j)=1 for all j; res X=res(Σ(res(xj))); andres X=res(x0+x1+ . . . +xn).
A modulus-15 generator may be implemented by using a counter tree such as a 3:2 counter tree similar to a multiplier's implementation. This may be costly in terms of area and delay.
With the advent of complementary metal oxide semiconductor (CMOS), modulus-3 checking systems have become popular due to their speed and size. In addition, CMOS appears to have fewer transient fails and therefore, may not need as high a degree of checking as that provided by the modulus-15 generator. Modulus-3 checking systems reduce a base-4 system as shown below:X=Σxi4i;res X=res(Σres(res(xi)res(4i))), where res(4i)=1 for all i; res X=res(Σ(res(xi))); andres X=res(x0+x1+ . . . +xn).
A modulus-3 system may also be utilized for checking a base-10 system since every power of 10 has a remainder of 1 when divided by 3. So, just like the binary system, groups of 2 bits can be summed together in the form of a counter tree. A faster implementation of modulus-3 that uses pass-gate multiplexers that are extremely small and fast may also be utilized.
It would be desirable to have a residue generator with the speed of a modulus-3 system with the greater checking capabilities of a higher radix modulus.